1. Field of the Invention
The present application relates to database processing, more particularly to the sort function in database processing.
2. State of the Art
Sort is a fundamental operation in databases. Query requests for data often require data to be ordered based on some criterion. When a query request requires an order based on a criterion that is not already provided in some existing database index, the database planner must decide between two alternatives: 1.) Create an index (perhaps temporarily) to be used to compute the ordering. 2.) Sort the result rows as they are computed by applying the desired ordering criterion. The present application addresses the second option, which is often a good option when some combination of the following conditions apply: 1.) It is known that a particular query ordering is not likely to be re-used soon. 2.) The overhead of the index is high.
Often database sort requests only require the first L results; nevertheless, existing mechanisms require the data to be fully sorted before any results can be returned.